﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>
using namespace std;

#if 0


//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
//不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。


//class Solution {
//public:
//    void reverseString(vector<char>& s) 
//    {
//       /* char ch;
//        while (cin.get(ch) && ch != '\n')
//        {
//            s.push_back(ch);
//        }
//        reverse(s.begin(), s.end());
//        for (char ch : s)
//        {
//            cout << ch;
//        }
//        cout << endl;*/
//        reverse(s.begin(), s.end());
//    }
//};



//给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

//如果剩余字符少于 k 个，则将剩余字符全部反转。
//如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样


class Solution {
public:
    string reverseStr(string s, int k) 
    {
        string::iterator left = s.begin();//初始左区间


        while (left < s.end())
        {
            //初始右区间
            string::iterator right = (left + 2 * k) < s.end() ? left + 2 * k : s.end();

            //确定右区间的实际值
            //剩余数量小于k，就全部反转；剩下数量大于k，就反转前k
            string::iterator rightend = (left + k) < s.end() ? (left + k) : s.end();

            reverse(left, rightend);

            //移动
            left = right;

        }
        return s;
    }
};


//字符串最后一个单词的长度

//对于给定的若干个单词组成的句子，每个单词均由大小写字母混合构成，单词间使用单个空格分隔。输出最后一个单词的长度。


//int main() 
//{
//    string s;
//    
//    getline(cin, s);//读取一行
//    int last = s.rfind(" "); //读取最后一个空格的下标
//    int ret = s.size() - (last + 1);
//    cout << ret << endl;
//}



//如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
//
//字母和数字都属于字母数字字符。
//
//给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false


class Solution {
public:
    bool isPalindrome(string s) //第一种方式 将字母数字连接到新的string
    {
        string tmp;
        string::iterator left = s.begin();
        string::iterator right = s.end();

        while (left != right)//第一次遍历，所有字母数字转入新string，并且统一为小写
        {
            if ((*left >= '0' && *left <= '9') || (*left >= 'a' && *left <= 'z'))
                tmp += *left;
            if (*left >= 'A' && *left <= 'Z')
                tmp += (*left + 32);
            ++left;
        }

        if (tmp.empty())//如果新string为空，则判定为回文串
            return true;

        left = tmp.begin();
        right = tmp.end() - 1;
        while (left <= right)//第二次遍历 左右迭代器逐个对比
        {
            if (*left == *right)
            {
                ++left;
                --right;
            }
            else
                return false;
        }
        return true;
    }
};


class Solution {
public:
    bool isPalindrome(std::string s) //第二种方式，直接原地筛选判断
    {
        string::iterator left = s.begin();
        string::iterator right = s.end() - 1;

        while (left < right)
        {
            // 跳过左边的非字母数字字符
            while (left < right && !isalnum(*left))
            {
                ++left;
            }
            // 跳过右边的非字母数字字符
            while (left < right && !isalnum(*right))
            {
                --right;
            }

            if (left < right) {
                // 将字符转换为小写后比较
                if (tolower(*left) != tolower(*right))
                {
                    return false;
                }
                ++left;
                --right;
            }
        }
        //跳出循环，要么left==right,要么left>right 
        //说明所有需要比较的字符对都已经检查过，且都相等
        return true;
    }
};


﻿/*int main(int argc, char* argv[])

{

    string strText = "How are you?";

    string strSeparator = " ";

    string strResult;

    int size_pos = 0;

    int size_prev_pos = 0;

    while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)

    {

        strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);

        cout << strResult << " ";

        size_prev_pos = ++size_pos;

    }

    if (size_prev_pos != strText.size())

    {

        strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);

        cout << strResult << " ";

    }

    cout << endl;

    return 0;

}*/


//请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）
//class Solution {
//public:
//    int myAtoi(string str)
//    {
//        int flag = 1;//正负号
//        int i = 0;   //下标
//        int ret = 0; //结果
//        int size = str.size();
//        while (i < size)
//        {
//            if (str[i] == '-')
//                flag = -1;
//            if (str[i] >= '0' && str[i] <= '9')
//            {    //获取到一个数字，开始计入结果，直到出现非数字停止
//                while ((i < size) && (str[i] >= '0' && str[i] <= '9'))
//                {
//                    ret = ret * 10 + (str[i] - '0');
//                    ++i;
//                }
//                return flag * ret;
//            }
//            ++i;
//        }
//        return flag * ret;
//
//    }
//};



//class Solution {
//public:
//    int myAtoi(string str)
//    {
//        int flag = 1;//正负号
//        int i = 0;   //下标
//        int ret = 0; //结果
//        int size = str.size();
//
//        // 忽略前导空格
//        while (i < size && str[i] == ' ') {
//            ++i;
//        }
//
//        // 处理符号
//        if (i < size && str[i] == '-') {
//            flag = -1;
//            ++i;
//        }
//        else if (i < size && str[i] == '+') {
//            ++i;
//        }
//
//        // 转换数字
//        while (i < size && str[i] >= '0' && str[i] <= '9') {
//            int digit = str[i] - '0';
//            // 检查溢出
//            if (ret > (INT_MAX - digit) / 10) {
//                return flag == 1 ? INT_MAX : INT_MIN;
//            }
//            ret = ret * 10 + digit;
//            ++i;
//        }
//
//        return flag * ret;
//
//    }
//};


//int main1(int argc, char* argv[])
//{
//    string strText = "How are you?";
//    string strSeparator = " ";
//    string strResult;
//
//    int size_pos = 0;//类似前指针
//    int size_prev_pos = 0;//类似后指针
//
//    while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
//                  //从How are you?里面找空格的下标，赋值给size_pos，如果不是最大值，就继续循环
//    {
//        strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);//取前后指针中间的部分
//        cout << strResult << " "; //打印该部分，再打印空格
//        size_prev_pos = ++size_pos;  //，前指针+1，后指针挪到前指针的位置
//    }
//
//    if (size_prev_pos != strText.size())//如果后指针没有移动到结尾\0位置
//    {
//        strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);//取剩下部分
//        cout << strResult << " ";//打印该部分，再打印空格
//    }
//    cout << endl;
//    return 0;
//}

//﻿int main2(int argc, char* argv[])
//{
//    string a = "hello world";
//    string b = a;//"hello world"
//
//    //c_str() 成员函数用于返回一个指向以 null 结尾的字符数组的指针
//    // 这个字符数组包含了 std::string 对象中的字符串内容
//
//    if (a.c_str() == b.c_str())//两个指针不同，指向内容相同
//                                //这里比较的是两个指针而不是内容
//                                //两个string对象直接比较，比较的是字符串的内容
//    {
//        cout << "true" << endl;
//    }
//    else cout << "false" << endl;
//
//    string c = b;  //"hello world"
//    c = ""; //空
//    if (a.c_str() == b.c_str())// a和b相比上面没有任何变化，所以两个指针不同，指向内容相同
//    {
//        cout << "true" << endl;
//    }
//    else cout << "false" << endl;
//
//    a = "";//空
//    if (a.c_str() == b.c_str())
//    {
//        cout << "true" << endl;
//    }
//    else cout << "false" << endl;
//    return 0;
//}

//﻿int main(int argc, char* argv[])
//{
//    string str("Hello Bit.");
//    str.reserve(111);  //size  不变    capacity  111以上
//    str.resize(5);      //size  5   capacity    不变 111
//    str.reserve(50);    //size   不变 5   capacity   不变111 因为50小于原本的容量 所以不变
//    cout << str.size() << ":" << str.capacity() << endl;   //5   111
//    return 0;
//}


//给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

//输入： s = "Mr Ding"
//输出："rM gniD"

class Solution {
public:
    string reverseWords(string s) //快慢指针解法
    {
        string::iterator fast = s.begin();
        string::iterator slow = s.begin();

        while (fast != s.end())//快指针走完就结束
        {
            if (*fast == ' ') //快指针走到空格位置停下，反转该部分字母
            {
                reverse(slow, fast);
                slow = fast + 1;
            }
            ++fast;
        }
        reverse(slow, fast);//出循环时，慢指针留在最后一个单词的第一个字母
        //快指针在\0位置，还需要反转一次
//同时可以对只要一个单词的string处理
        return s;

    }
};


#endif

#if 0
class Solution {
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0")//先判断是否有一个为0
            return "0";

        reverse(num1.begin(), num1.end());//反转两个字符串方便操作
        reverse(num2.begin(), num2.end());

        int size = num1.size() + num2.size();//结果位数不超过两个字符串之和

        int* ret = new int[size]();//创建存储结果的数组并初始化为0
        // for(int i =0;i<size;++i)
        // {
        //     ret[i]=0;
        // }

        for (int i = 0; i < num1.size(); ++i)//字符串相乘，不考虑进位
        {
            for (int j = 0; j < num2.size(); ++j)
            {
                ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        for (int i = 0; i < size - 1; ++i)//处理进位
        {
            ret[i + 1] += ret[i] / 10;
            ret[i] = ret[i] % 10;
        }

        int i = size - 1;
        while ((ret[i] == 0) && (size > 1))//去除前导零
        {
            --size;
            --i;
        }

        string s = "";
        s.reserve(size + 1);
        for (int i = size - 1; i >= 0; --i)//转字符串
        {
            s += ('0' + ret[i]);
        }

        delete[]ret;
        return s;

    }
};

#endif

//给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 
//s 只包含小写字母

class Solution {
public:
    int firstUniqChar(string s) //暴力解法
    {
        int size = s.size();
        for (int i = 0; i < size; ++i)
        {
            int flag = 1;
            for (int j = 0; j < size; ++j)
            {
                if ((s[i] == s[j]) && (i != j))//如果有相同的字符，就结束这轮对比
                {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)//循环走完，标志没有被改变，说明没有相同的字符
                return i;
        }
        return -1;
    }
};

class Solution {
public:
    int firstUniqChar(string s) //计数排序解法
    {
        int count[26];//创建数组映射存储次数
        int size = s.size();

        for (int i = 0; i < size; ++i)//第一次遍历，记录次数
        {
            ++count[s[i] - 'a'];
        }

        for (int i = 0; i < size; ++i)//第二次遍历，找到第一个只出现一次的字母
        {
            if (count[s[i] - 'a'] == 1)
                return i;
        }

        return -1;//走到这里说明不存在
    }
};

int main()
{
    //string s1("123");
    //string s2("456");
    //Solution s;
    ////cout<<s.multiply(s1, s2)<<endl;
    
    return 0;
}